package com.zlk.algorithm.huawei.leetcode.list;

import com.zlk.algorithm.util.ListNode;

/**
 * @program: algorithm
 * @ClassName Code91_detectCycle
 * @description:
 * @author: slfang
 * @create: 2025-01-07 16:41
 * @Version 1.0
 **/
public class Code19_detectCycle {

    /// 方法1：可以用HashSet 容器方法
    // 方法2：直接记这个流程 不用管流程
    // 首先快慢指针相遇
    // 然后f 回到原来head 位置
    // 然后s1步  f一步
    // 然后一定会在环的第一个节点相遇
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return null;
        }
        ListNode slow = head.next;
        ListNode fast = head.next.next;
        while (slow != fast) {
            if (fast.next == null || fast.next.next == null) {
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        fast = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

}
